/**
    Copyright (c) 2009 yakiimo02
    Distributed under the New BSD License.
    See included license.txt or http://www.yakiimo3d.com/NewBSDLicense.txt
**/

#include "DXUT.h"
#include "BitonicSortRecursiveCPU.h"

/**
    Sort m_data in increasing order.
*/
void BitonicSortRecursiveCPU::SortUp() 
{ 
    SortUp( 0, m_data.size() ); 
    CheckSortUp( m_data );
}

/**
    Sort m_data in decreasing order.
*/
void BitonicSortRecursiveCPU::SortDown() 
{ 
    SortDown( 0, m_data.size() ); 
    CheckSortDown( m_data );
}

/**
    @param nBegin    index of first element to sort
    @param nCount    numbers of elements to sort
*/
void BitonicSortRecursiveCPU::SortUp( int nBegin, int nCount ) 
{
    if ( nCount==1 ) { 
        return; 
    }
    
    // first half
    SortUp( nBegin, nCount/2 );
    
    // last half
    SortDown( nBegin+nCount/2, nCount/2 );
    
    MergeUp( nBegin, nCount/2 );
}

/*
    @param nBegin    index of first element to sort
    @param nCount    numbers of elements to sort
*/
void BitonicSortRecursiveCPU::SortDown( int nBegin, int nCount ) 
{
    if ( nCount==1 ) { 
        return; 
    }

    // first half
    SortUp( nBegin, nCount/2 );
    
    // last half
    SortDown( nBegin+nCount/2, nCount/2 );
    
    MergeDown( nBegin, nCount/2 );
}

/*
    @param nBegin    index of first element to sort
    @param nCount    numbers of elements to sort
*/
void BitonicSortRecursiveCPU::MergeUp( int nBegin, int nCount ) 
{
    if( nCount ==0 ) {
        return;
    }

    for( int nIndex=0; nIndex<nCount; ++nIndex ) 
    {
        if( m_data[ nBegin+nIndex ] > m_data[ nBegin+nIndex+nCount ] )
        {            
            Swap( nBegin+nIndex, nBegin+nIndex+nCount );
        }
    }

    MergeUp( nBegin, nCount/2 );

    MergeUp( nBegin+nCount, nCount/2 );
}

/*
    @param nBegin    index of first element to sort
    @param nCount    numbers of elements to sort
*/
void BitonicSortRecursiveCPU::MergeDown( int nBegin, int nCount ) 
{
    if( nCount ==0 ) {
        return;
    }

    for( int nIndex=0; nIndex<nCount; ++nIndex ) 
    {
        if( m_data[ nBegin+nIndex ] < m_data[ nBegin+nIndex+nCount ] )
        {            
            Swap( nBegin+nIndex, nBegin+nIndex+nCount );
        }
    }

    MergeDown( nBegin, nCount/2 );

    MergeDown( nBegin+nCount, nCount/2 );
}

